home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 1258 < prev    next >
Encoding:
Text File  |  1996-08-06  |  3.1 KB  |  73 lines
  1. Path: news.uoregon.edu!xmission!news
  2. From: tknarr@xmission.com  ( Todd Knarr )
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: deque container - how to implement?
  5. Date: 10 Jan 1996 04:20:15 GMT
  6. Organization: Chaos Central
  7. Message-ID: <4cvepv$5rn@news.xmission.com>
  8. References: <4ce651$92t@galaxy.uci.agh.edu.pl> <4ct0c3$9gg@news.bridge.net>
  9. Reply-To: tknarr@xmission.com ( Todd Knarr )
  10. NNTP-Posting-Host: slc133.xmission.com
  11. X-Newsreader: IBM NewsReader/2 v1.2
  12.  
  13. In <4ct0c3$9gg@news.bridge.net>, David Byrden <100101.2547@compuserve.com> writes:
  14. >I have hardly studied deque and have never seen an implementation, but I 
  15. >will bet that it works like this; it consists of a contigous block of 
  16. >elements in the MIDDLE of a larger block of free space. Adding elements 
  17. >is fast because there is free space at each end. When it expands to bump 
  18. >either end of its free space, it allocates a larger block of memory from 
  19. >the heap and copies all its contents into the MIDDLE of the new block. 
  20. >Altering things in the middle is slow because the elements must remian 
  21. >contiguous, so up to half of the data will need to move.
  22.  
  23. They can be implemented that way ( based on an array of elements ), but
  24. it's unusual because of the physical shuffling needed. More often they
  25. are implemented using pointers. For a deque of objects of class T, you
  26. make a node type like so ( for a fully non-intrusive list ):
  27.  
  28. struct Node
  29. {
  30.     Node *pNext, *pPrev;
  31.     T *pElement;
  32. };
  33.  
  34. You start out with head and tail pointers set to the first and last
  35. nodes in the list. Inserting an item simply involves making a new node
  36. for it, pointing that node's pNext and pPrev pointers to the nodes
  37. just before and after it in the list, then pointing those node's pNext
  38. and pPrev pointers to the new node as appropriate. As sample code,
  39. assuming pInsertPoint points to the node I want to insert after and
  40. pNewNode points to the node to insert with pElement filled in, I would
  41. do:
  42.  
  43. pNewNode->pPrev = pInsertPoint;
  44. pNewNode->pNext = pInsertPoint->pNext;
  45. pInsertPoint->pNext->pPrev = pNewNode;
  46. pInsertPoint->pNext = pNewNode;
  47.  
  48. Removing an element simply involves finding the node and cutting it out
  49. of the chain by pointing the pNext and pPrev pointers of the nodes before
  50. and after it to each other.
  51.  
  52. Implementation notes:
  53.  
  54. 1) The idea of a Node structure seperate from the element is solely to
  55. allow building lists of things without needing any fields in the things
  56. to be put on the list. You can also put the next and previous pointers
  57. in the actual items and avoid allocating and deallocating nodes all the
  58. time.
  59.  
  60. 2) Most implementations that use Node structures use two dummy nodes to
  61. anchor the head and tail of the list. They usually have NULL pElement
  62. pointers to distinguish them from real nodes. This eliminates special-case
  63. code to deal with an empty list or the ends of the list.
  64.  
  65. --
  66. Todd Knarr : tknarr@xmission.com      |  finger for PGP public key
  67.                                       |  Member, USENET Cabal
  68.  
  69. Seriously, I don't want to die just yet.  I don't care how
  70. good-looking they are, I! don't! want! to! die!"
  71.                                         -- Megazone ( UF1 )
  72.  
  73.